package ch09_;

public class Ch9_11 {
	public long count(String expr, boolean flag) throws Exception {
		char[] seq = expr.toCharArray();
		return count1(seq, 0, seq.length - 1, flag);
	}
	
	private long count1(char[] seq, int l, int r, boolean flag) throws Exception {
		if (l > r) {
			throw new Exception("l cannot be greater than r.");
		}
		if (l == r) {
			if (seq[l] == '1' && flag) {
				return 1;
			} else if (seq[l] == '0' && !flag) {
				return 1;
			} else {
				return 0;
			}
		}
		
		long result = 0;
		for (int i = l; i <= r; i++) {
			if (seq[i] == '&') {
				result += count1(seq, l, i - 1, true)
						* count1(seq, i + 1, r, true);
			} else if (seq[i] == '|') {
				long lt = count1(seq, l, i - 1, true);
				long lf = count1(seq, l, i - 1, false);
				long rt = count1(seq, i + 1, r, true);
				long rf = count1(seq, i + 1, r, false);
				result += lt * rf
						+ lf * rt
						+ lt * rt;
			} else if (seq[i] == '^') {
				long lt = count1(seq, l, i - 1, true);
				long lf = count1(seq, l, i - 1, false);
				long rt = count1(seq, i + 1, r, true);
				long rf = count1(seq, i + 1, r, false);
				result += lt * rf
						+ lf * rt;
			}
		}
		if (!flag) {
			int n = (r - l) / 2;
			result = catalan(n) - result;
		}
		return result;
	}
	
	
	
	private long catalan(int n) {
		long result = 1;
		for (int i = n + 1; i <= 2 * n; i++) {
			result *= i;
		}
		for (int i = 2; i <= n + 1; i++) {
			result /= i;
		}
		return result;
	}
	
	public static void main(String[] args) {
		Ch9_11 test = new Ch9_11();
		String expr = "1^0|0|1";
		boolean flag = false;
		long result = 0;
		try {
			result = test.count(expr, flag);
		} catch (Exception e) {
			e.printStackTrace();
		} finally {
			System.out.println(result);
		}
	}
}
